package org.example.myleet.p686;

public class Solution {

    /**
     * 官方思路：类KMP算法，参考p28
     * KMP算法思路：分两步走，第一步对目标字符串预处理，可以理解为做索引，第二步是目标字符串对文本内容的匹配搜索
     * 本题中，b是目标字符串，a是可以重复循环的文本，可以理解为无限长，因此和普通KMP不同之处在于需要对a的匹配作终止判断
     */
    public int repeatedStringMatch(String a, String b) {
        if (b.length() == 0) {
            //特殊情况讨论
            return 0;
        }
        if (b.length() == 1) {
            //特殊情况讨论
            char bc = b.charAt(0);
            for (char ac : a.toCharArray()) {
                if (ac == bc) {
                    return 1;
                }
            }
            return -1;
        }
        char[] ac = a.toCharArray();
        char[] bc = b.toCharArray();
        //下面预处理b得到next数组
        int[] next = new int[bc.length];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < bc.length;) {
            while (j > 0 && bc[j] != bc[i]) {
                j = next[j - 1];
            }
            if (bc[j] == bc[i]) {
                ++j;
            }
            next[i] = j;
            ++i;
        }
        //开始在重复的a中寻找b是否存在，用next数组加速
        j = 0;
        int i = 0;
        int end = 2 * ac.length;
        while (j < bc.length) {
            int i_ = i % ac.length;
            if (bc[j] != ac[i_] && i > end) {
                //特别的，当一次重复的a中仍未能匹配到b，说明是找不到
                return -1;
            }
            while (j > 0 && bc[j] != ac[i_]) {
                j = next[j - 1];
            }
            if (bc[j] == ac[i_]) {
                ++j;
            }
            ++i;
        }
        if (i <= ac.length) {
            return 1;
        }
        int remainder = i % ac.length;
        int repeatCount = i / ac.length;
        if (remainder > 0) {
            ++repeatCount;
        }
        return repeatCount;
    }

    /**
     * 暴力匹配，a每次匹配不上时就从下一个字符开始对b重新完全匹配
     */
//    public int repeatedStringMatch(String a, String b) {
//        if (b.length() == 0) {
//            return 0;
//        }
//        char[] ac = a.toCharArray();
//        char[] bc = b.toCharArray();
//        int ai = 0, bi = 0;
//        int repeatCount = 1;
//        int candidateAStart = 0;
//        while (bi < bc.length) {
//            if (ac[ai] == bc[bi]) {
//                ++ai;
//                ++bi;
//            } else {
//                if (candidateAStart >= ac.length) {
//                    return -1;
//                }
//                ai = candidateAStart + 1;
//                bi = 0;
//                repeatCount = 1;
//                candidateAStart = Math.max(candidateAStart, ai);
//            }
//            if (bi < bc.length && ai == ac.length) {
//                ai = 0;
//                ++repeatCount;
//            }
//        }
//        return repeatCount;
//    }
}
